﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习九月份
{
    public class SolutionSortArray
    {
        public int[] SortArrayCZH(int[] nums)
        {
            QuickSort(nums, 0, nums.Length - 1);
            return nums;
        }
        public void QuickSort(int[] nums, int left, int right)
        {
            if (left < right)
            {

                int pivot = Partition(nums, left, right);
                QuickSort(nums, left, pivot - 1);
                QuickSort(nums, pivot + 1, right);

            }

        }

        private int Partition(int[] nums, int left, int right)
        {

            int start = left;
            int end = right;
            int pivot = nums[left];

            while (start < end)
            {
                while (start < end && nums[start] <= pivot)
                {
                    start++;
                }
                while (start <= end && nums[end] >= pivot)
                {
                    end--;
                }

                if (start < end)
                {
                    MySwap(nums, start, end);

                }
            }

            MySwap(nums, start, left);
            return start;
        }

        private void MySwap(int[] nums, int left, int right)
        {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;


        }



        public int[] SortArray(int[] nums)
        {



            QuickSortArray(nums, 0, nums.Length - 1);
            return nums;



        }

        private void QuickSortArray(int[] nums, int left, int right)
        {
            int oldleft = left;
            int oldright = right;



            if (left > right)
            {
                return;
            }
            int randomIndex = (left + right) / 2;
            int val = nums[randomIndex];
            MySwap(nums, left, randomIndex);

            while (left < right)
            {
                while (left < right && nums[right] >= val)
                {
                    right--;
                }

                nums[left] = nums[right];

                while (left < right && nums[left] <= val)
                {
                    left++;
                }

                nums[right] = nums[left];

            }

            nums[left] = val;
            QuickSortArray(nums, oldleft, left - 1);
            QuickSortArray(nums, left + 1, oldright);
        }

    }


    class ProgramSort
    {
        static void MainSort(string[] args)
        {

           // int[] nums = [110, 100, 0];
            int[] nums = [5, 2, 3, 1];

            SolutionSortArray sol = new SolutionSortArray();
            int[] res = sol.SortArray(nums);
            for (int i = 0; i < res.Length; i++)
            {
                Console.Write(res[i] + ",");
            }
            Console.WriteLine();
        }


    }
}
